import java.util.*;

public class BinaryHeap<T> implements Heap<T> {
    private Comparator<T> comparator;

    private Vector<T> elements;

    public BinaryHeap(Comparator<T> comparator) {
        this();
        this.comparator = comparator;
    }

    public BinaryHeap(T[] elements, Comparator<T> comparator) {
        this.elements = new Vector<>(Arrays.asList(elements));
        this.comparator = comparator;

        heapify_shiftDown();
    }

    public BinaryHeap() {
        elements = new Vector<>();
    }

    @Override
    public void add(T element) throws Exception {
        if (elements.add(element)) {
            siftUp(elements.size() - 1);
        } else {
            throw new Exception("Fail to add element:" + element);
        }
    }

    @Override
    public T remove() {
        try {
            T lastElement = elements.lastElement();
            T topElement = elements.set(0, lastElement);
            elements.removeElementAt(elements.size() - 1);

            siftDown(0);

            return topElement;
        } catch (ArrayIndexOutOfBoundsException e) {
            e.printStackTrace();
        }
        return null;
    }

    @Override
    public T get() {
        try {
            return elements.firstElement();
        } catch (NoSuchElementException e) {
            e.printStackTrace();
        }
        return null;
    }

    @Override
    public void clear() {
        elements.clear();
    }

    @Override
    public int size() {
        return elements.size();
    }

    @Override
    public boolean isEmpty() {
        return elements.isEmpty();
    }

    private void siftDown(int index) {
        int targetChildIndex;

        while (true) {
            int leftChildIndex = index * 2 + 1;
            if (leftChildIndex <= size() - 1) {
                T leftChild = elements.get(leftChildIndex);
                targetChildIndex = leftChildIndex;

                int rightChildIndex = leftChildIndex + 1;
                if (rightChildIndex <= size() - 1) {
                    T rightChild = elements.get(rightChildIndex);
                    targetChildIndex = comparator.compare(leftChild, rightChild) < 0 ? leftChildIndex : rightChildIndex;
                }
            } else {
                // 无左子树
                break;
            }

            T element = elements.get(index);
            T targetChildElement = elements.get(targetChildIndex);
            if (comparator.compare(element, targetChildElement) <= 0) {
                break;
            } else {
                Collections.swap(elements, targetChildIndex, index);
                index = targetChildIndex;
            }
        }
    }

    private void siftUp(int index) {
        T temp = elements.get(index);
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            T parentElement = elements.get(parentIndex);
            if (comparator.compare(temp, parentElement) < 0) {
                elements.setElementAt(parentElement, index);
                index = parentIndex;
            } else {
                break;
            }
        }
        elements.setElementAt(temp, index);
    }

    private void heapify_shiftUp() {
        for (int i = 1; i < size(); i++) {
            siftUp(i);
        }
    }

    private void heapify_shiftDown() {
        for (int i = (size() >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    public boolean isHeap() {
        return isHeap(0);
    }

    private boolean isHeap(int rootIndex) {
        int leftChildIndex = 2 * rootIndex + 1;
        if (leftChildIndex <= size() - 1) {
            final T rootElement = elements.get(rootIndex);
            if (comparator.compare(rootElement, elements.get(leftChildIndex)) <= 0) {
                int rightChildIndex = leftChildIndex + 1;
                if (rightChildIndex <= size() - 1) {
                    if (comparator.compare(rootElement, elements.get(rightChildIndex)) <= 0) {
                        return isHeap(leftChildIndex) && isHeap(rightChildIndex);
                    } else {
                        return false;
                    }
                } else {
                    return true;
                }

            } else {
                return false;
            }
        } else {
            return true;
        }
    }
}
